Philosophenproblem

Philosophenproblem,

 

klassisches Problem zur Erläuterung nebenläufiger Prozesse und damit zusammenhängender Begriffe wie Verklemmung, Semaphor usw. (Nebenläufigkeit). Zugleich verdeutlicht das Problem die Unüberschaubarkeit bereits sehr einfacher nebenläufiger Strukturen.

 

Fünf Philosophen sitzen rund um einen Tisch. Vor jedem Philosophen steht ein Teller mit einer Portion Spaghetti und zwischen jedem Teller liegt eine Gabel. Jeder Philosoph beschäftigt sich nun eine Weile mit Nachdenken, bis er hungrig wird und zum Essen schreiten will. Man geht davon aus, dass ein Philosoph zum Essen zwei Gabeln benötigt, nämlich die links und rechts neben seinem Teller liegenden. Offenbar können also höchstens zwei Philosophen gleichzeitig essen, da nicht mehr als fünf Gabeln zur Verfügung stehen.

 

Möchte man die vorhandene Situation und das Verhalten der Philosophen in ein Programm umsetzen, muss man berücksichtigen, dass der von zwei benachbarten Philosophen unternommene gleichzeitige Zugriff auf eine Gabel einen Konflikt auslösen würde. Dieser Konflikt muss durch Kontrollvariablen vermieden werden (programmtechnisch durch Semaphore). Sie kennzeichnen, ob eine Gabel bereits belegt ist oder nicht; das Programm gibt nur eine gemäß der Kontrollvariablen freie Gabel an einen Philosophen heraus, bei absolut gleichzeitigem Zugriff auf eine freie Gabel wird eine Reihenfolge vereinbart.

 

Wenn das Programm die Lösung von Konflikten beherrscht, kann es dennoch zu Verklemmungen kommen. Werden z. B. alle Philosophen gleichzeitig hungrig und ergreifen zunächst jeweils ihre linke Gabel, kann kein Philosoph mit dem Essen beginnen oder sonst noch irgendeine Tätigkeit ausführen. Um diese Situation zu verhindern, müssen weitere Kontrollvariablen eingeführt werden. Diese kennzeichnen, ob ein Philosoph denkt, isst oder hungrig zu den Gabeln greifen möchte. Durch einige Abfragen kann nun gesichert werden, dass zwei benachbarte Philosophen sich nicht gleichzeitig auf das Essen vorbereiten.

 

Auch eine Lösung, die alle Verklemmungen beseitigt, muss nicht unbedingt befriedigend sein. So kann das sog. Fairnessproblem auftauchen, dass nämlich ein Philosoph durch das Verhalten seiner beiden Nachbarn vom Essen abgehalten wird und verhungert. Dieser Fall tritt z. B. ein, wenn beide Nachbarn niemals gleichzeitig nachdenken, sondern immer abwechselnd denken und essen. Die Beseitigung dieser Schwierigkeiten ist nicht unkompliziert und erfordert erhebliche Verbesserungen des Algorithmus.